package leetcode;

import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/11/19 0019.
 */
public class Combination {
    LinkedList<Integer> list = new LinkedList<Integer>();
    List<List<Integer>> rst = new LinkedList<List<Integer>>();
    private void comb(int[] N,int begin,int k){
        if(k==0){
            LinkedList<Integer> tmp = new LinkedList<Integer>();
            tmp.addAll(list);
            rst.add(tmp);
        }
        else{
            for(int i=begin;i<=N.length-k;i++){
                list.add(N[i]);
                comb(N,i+1,k-1);
                list.removeLast();
            }
        }
    }
    public List<List<Integer>> combine(int n, int k) {
        if(n<k)
            return rst;
        int[] N = new int[n];
        for(int i=0;i<n;i++){
            N[i] = i+1;
        }
        comb(N,0,k);
        return rst;
    }
    public static void main(String[] args){
        Combination combination = new Combination();
        List<List<Integer>> list = combination.combine(4,5);
        for(List l:list){
            for(Object ii:l){
                System.out.print(" "+ii);
            }
            System.out.println();
        }
    }
}
